package com.datastructure.test.recall.haverepeatnumberarray;

import java.util.*;

public class HaveRepeatNumberArray {

    ArrayList<ArrayList<Integer>> data = new ArrayList<>();
    public static void main(String[] args) {
        HaveRepeatNumberArray haveRepeatNumberArray = new HaveRepeatNumberArray();
        Deque<Integer> deque = new ArrayDeque<>();
        int[] temp = {0,-1};
        Arrays.sort(temp);
        int length = temp.length;
        boolean[] used = new boolean[length];
        haveRepeatNumberArray.dfs(0, length, temp, deque, used);
        for (int i = 0; i < length; i++) {
            int finalI = i;
            haveRepeatNumberArray.data.stream().sorted((list1,list2) -> {
                if(list1.get(finalI)>list2.get(finalI)){
                    return 1;
                } else if(list1.get(finalI)<list2.get(finalI)){
                    return -1;
                }
                return 0;
            });
        }
        System.out.println(haveRepeatNumberArray.data);
    }

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Deque<Integer> deque = new ArrayDeque<>();
        int length = num.length;
        boolean[] used = new boolean[length];
        dfs(0, length, num, deque, used);
        for (int i = 0; i < length; i++) {
            int finalI = i;
            data.stream().sorted(Comparator.comparingInt(list -> list.get(finalI)));
        }
        return data;
    }

    public void dfs(int depth, int length, int[] res, Deque<Integer> deque,boolean[] used){
        if(depth==length){
            data.add(new ArrayList<>(deque));
            return;
        }
        for(int i = 0;i< res.length;i++){
            if(used[i]){
                continue;
            }
            if(i>0&&res[i]==res[i-1]&&!used[i-1]){
                continue;
            }
            used[i] = true;
            deque.add(res[i]);
            dfs(depth+1,length,res,deque,used);
            used[i] = false;
            deque.removeLast();
        }
    }
}
